package sort;

public class Shell {
	
	public static void sort(Comparable arr[]) {
		//初始化增量值h
		int h = 1;
		while(h<arr.length/2) {
			h = 2*h + 1;
		}
		while(h>=1) {
			//找到待插入的元素
			for(int i=h;i<arr.length;i++) {
				for(int j=i;j>=h;j-=h) {
					//排序
					if(greater(arr[j],arr[j-h])){
						swap(arr,j,j-h);
					}else {
						break;
					}
				}			
			}	
			//减少排序的增量
			h = h/2;
		}
		
		
		
		
	}
	
	private static boolean greater(Comparable a,Comparable b) {
		return (a.compareTo(b)>0);
	}
	
	private static void swap(Comparable arr[],int i,int j) {
		Comparable temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}
